
import java.util.ArrayList;
import java.util.Arrays;

/** Classe que efectua as jogadas da IA.
 *
 * @author ei08150
 */

class ComputerAI {

	static private final int EASY_DEPTH = 2;
	static private final int MEDIUM_DEPTH = 3;
	static private final int HARD_DEPTH = 4;

	static private final int INFINITY = Integer.MAX_VALUE-2;

	/** Recebe um tabuleiro e devolve uma jogada (recorrendo ao algoritmo Minimax com cortes Alfa-Beta).
	 * @param currentBoard O tabuleiro actual.
	 * @param player Jogador que vai efectuar a jogada.
	 * @param playerType Tipo (dificuldade) do jogador.
	 * @returns Jogada que o computador escolheu.
	 */
	static public Move makeMove(Board currentBoard, int player, int playerType) {
		switch(playerType) {
			case Player.CPU_EASY:
				return minimax(currentBoard, EASY_DEPTH, player);
			case Player.CPU_MEDIUM:
				return minimax(currentBoard, MEDIUM_DEPTH, player);
			case Player.CPU_HARD:
				return minimax(currentBoard, HARD_DEPTH, player);
			default:
				return null;
		}
	}

	/** Função que inicia o algoritmo Minimax, com cortes Alfa-Beta, para encontrar a
	 * melhor jogada (que conseguir) a ser feita.
	 * @param board O tabuleiro actual.
	 * @param depth Profundidade máxima do algoritmo.
	 * @param player Jogador actual.
	 * @return Jogada a ser feita
	 */
	static private Move minimax(Board board, int depth, int player) {
		// A jogada devolvida será escolhida de entre as melhores jogadas (com pontuação máxima)
		ArrayList<Move> bestMoves = new ArrayList<Move>();
		int alpha = -INFINITY;
		int beta = INFINITY;
		int value;
		int otherPlayer = Hex.otherPlayer(player);
		int newDepth = depth - 1;

		for(int l = 0; l < board.getSize(); l++)
			for(int c = 0; c < board.getSize(); c++)
				if(board.isPositionEmpty(l, c)) {
					// Efectuar a jogada
					Board newBoard = board.clone();
					Move m = new Move(l, c);
					newBoard.placePiece(player, m);
					value = minimax(newBoard, newDepth, alpha, beta, otherPlayer, player);

					if(value == alpha)
						bestMoves.add(m);
					else if(value > alpha) {
						bestMoves.clear();
						bestMoves.add(m);
						alpha = value;
					}
				}

		// Escolher aleatoriamente (de entre as melhores) uma jogada
		int index = (int)(Math.random() * (double)bestMoves.size());
		return bestMoves.get(index);
	}

	/** Algoritmo Minimax, com cortes Alfa-Beta, para encontrar a
	 * melhor jogada (que conseguir) a ser feita.
	 * @param board O tabuleiro a ser analisado.
	 * @param depth Profundidade actual.
	 * @param alpha Valor alpha no momento.
	 * @param beta Valor beta no momento.
	 * @param player Jogador actual.
	 * @param maxPlayer Jogador "maximizante".
	 * @return Valor do tabuleiro para o jogador "maximizante".
	 */
	static private int minimax(Board board, int depth, int alpha, int beta, int player, int maxPlayer) {
		if(depth == 0 || board.isGameOver())
			return calculateBoardHeuristicValue(board, maxPlayer);
		else {
			int newDepth = depth - 1;
			int otherPlayer = Hex.otherPlayer(player);

			if(player == maxPlayer) {
				for(int l = 0; l < board.getSize(); l++)
					for(int c = 0; c < board.getSize(); c++)
						if(board.isPositionEmpty(l, c)) {
							Board newBoard = board.clone();
							Move m = new Move(l, c);
							newBoard.placePiece(player, m);
							alpha = Math.max(alpha, minimax(newBoard, newDepth, alpha, beta, otherPlayer, maxPlayer));

							if(beta <= alpha)
								break;
						}
				return alpha;
			}
			else {
				for(int l = 0; l < board.getSize(); l++)
					for(int c = 0; c < board.getSize(); c++)
						if(board.isPositionEmpty(l, c)) {
							Board newBoard = board.clone();
							Move m = new Move(l, c);
							newBoard.placePiece(player, m);
							beta = Math.min(beta, minimax(newBoard, newDepth, alpha, beta, otherPlayer, maxPlayer));

							if(beta <= alpha)
								break;
						}
				return beta;
			}
		}
	}

	static private int calculateBoardHeuristicValue(Board board, int player) {
		int boardValue = 0;

		final int boardValueWin = 50000;
		final int boardValueLose = 100000;

		// Serve so para indicar se devemos imprimir algumas
		// informacoes extra sobre o algoritmo
		boolean printDebug = false;
		// Ver se isto e um tabuleiro que termine o jogo
		if (player == Color.WHITE) {
			if (board.hasWhiteWon()) {
				boardValue += boardValueWin;
				printDebug = true;
			}
			else if (board.hasBlackWon()) {
				boardValue -= boardValueLose;
				printDebug = true;
			}
		}
		else {
			if (board.hasBlackWon()) {
				boardValue += boardValueWin;
				printDebug = true;
			}
			else if (board.hasWhiteWon()) {
				boardValue -= boardValueLose;
				printDebug = true;
			}
		}

		// Pecas nos cantos com angulos agudos sao mau sinal
		boardValue += numberOfPiecesInSharpCorners(board, player) * -100;

		int centerLine = board.getSize()/2;
		int centerColumn = board.getSize()/2;

		// So existe casa no centro do tabuleiro nos tabuleiro com tamanho impar
		if ((board.getSize() % 2) == 1) {
			if (board.getBoard()[centerLine][centerColumn] == player)
				boardValue += 1000;
			else if (board.getBoard()[centerLine][centerColumn] == Hex.otherPlayer(player))
				boardValue -= 1000;
		}

		// Tentar fazer as duas pontes
		boardValue += numberOfTwoBridges(board, player) * 100;
		boardValue -= numberOfTwoBridges(board, Hex.otherPlayer(player)) * -100;

		// if (printDebug) {
		// 	System.out.println(board);

		// 	for (int[] line : board.getBoard()) {
		// 		System.out.println(Arrays.toString(line));
		// 	}
		// 	System.out.println("Valor actual do boardValue: " + boardValue);
		// }
		return boardValue + (int)(Math.random() * 10.0);
	}

	static private int numberOfPiecesInSharpCorners(Board board, int player) {
		int piecesInCorner = 0;

		if (board.getBoard()[0][0] == player)
			piecesInCorner++;
		if (board.getBoard()[board.getSize()-1][board.getSize()-1] == player)
			piecesInCorner++;

		return piecesInCorner;
	}

	static private int numberOfTwoBridges(Board board, int player) {
		int numberOfTwoBridges = 0;

		// A representacao interna do tabuleiro
		int[][] internalRepresentation = board.getBoard();

		/* Situacao em que ocurre "2 pontes":
		 * (Assumindo que o 0 representa casas vazias, o 1 representa
		 * a peca que se estava a verificar e o 2 representa as casas
		 * com as quais faz "2 pontes")
		 *
		 * 00020
		 * 02002
		 * 00100
		 * 20020
		 * 02000
		 */
		for (int line = 0; line != internalRepresentation.length; line++) {
			for (int column = 0; column != internalRepresentation[0].length; column++) {
				numberOfTwoBridges += countNumberOfTwoBridgesFromPosition(board, line, column, player);
			}
		}

		return numberOfTwoBridges;
	}

	static private int countNumberOfTwoBridgesFromPosition(Board board, int line, int column, int player) {
		// A representacao interna do tabuleiro
		int[][] internalRepresentation = board.getBoard();

		/* Para fazer estes testes e necessario que os argumentos line
		 * e column indiquem uma posicao do tabuleiro preenchida pelo
		 * o mesmo jogador que o passado pelo argumento player
		 */
		if (internalRepresentation[line][column] != player) {
			return 0;
		}

		int numberOfTwoBridges = 0;

		/* Para que o computador consiga fazer "2 pontes" com as casas
		 * de limite do tabuleiro, ou seja, para que possa acontecer
		 * esta situacao (onde 1 representa a casa onde a jogada vai
		 * ser efectuada, 0 representa as casas vazias, 2 representa o
		 * *exterior* do tabuleiro e 3 representa as casas que estão
		 * ligadas ao limite do tabuleiro):
		 *
		 * 0002
		 * 0032
		 * 0132
		 * 0002
		 *
		 * E criado um tabuleiro temporario com o tamanho do tabuleiro
		 * passado pelo argumento board + 2 e com a seguinte
		 * disposicao (onde 1 representam as pecas pretas, 2
		 * representam as pecas brancas e _ representam as pecas do
		 * tabuleiro passado pelo argumento board, assumindo um
		 * tabuleiro com tamanho 4):
		 * 
		 * 122222
		 * 1____1
		 * 1____1
		 * 1____1
		 * 1____1
		 * 122222
		 *
		 * Em modo grafico, o tabuleiro teria este aspecto:
		 *
		 * O X X X X X     
		 *  O _ _ _ _ O    
		 *   O _ _ _ _ O   
		 *    O _ _ _ _ O  
		 *     O _ _ _ _ O 
		 *      O X X X X X
		 */
		int temporaryBoardSize = board.getSize() + 2;
		
		Board temporaryBoard = new Board(temporaryBoardSize);

		for (int tempLine = 0; tempLine != temporaryBoardSize; tempLine++) {
			for (int tempColumn = 0; tempColumn != temporaryBoardSize; tempColumn++) {
				// Canto superior esquerdo
				if (tempLine == 0 && tempColumn == 0) {
					temporaryBoard.placePiece(Color.WHITE, new Move(0, 0));
				}
				// Canto inferior esquerdo
				else if (tempLine == temporaryBoardSize-1
						 && tempColumn == 0) {
					temporaryBoard.placePiece(Color.WHITE, new Move(tempLine, 0));
				}
				// Canto superior direito
				else if (tempLine == 0
						 && tempColumn == temporaryBoardSize-1) {
					temporaryBoard.placePiece(Color.BLACK, new Move(0, tempColumn));
				}
				// Canto inferior direito
				else if (tempLine == temporaryBoardSize-1
						 && tempColumn == temporaryBoardSize-1) {
					temporaryBoard.placePiece(Color.BLACK, new Move(tempLine, tempColumn));
				}
				// Linha superior ou linha inferior
				else if (tempLine == 0
						 || tempLine == temporaryBoardSize-1) {
					temporaryBoard.placePiece(Color.BLACK, new Move(tempLine, tempColumn));
				}
				// Coluna da esquerda ou coluna da direita
				else if (tempColumn == 0
						 || tempColumn == temporaryBoardSize-1) {
					temporaryBoard.placePiece(Color.WHITE, new Move(tempLine, tempColumn));
				}
				// Pecas que vem do tabuleiro original
				else {
					// Converter tempLine e tempColumn para coordenadas do tabuleiro original
					int originalLine = tempLine - 1;
					int originalColumn = tempColumn - 1;
					temporaryBoard.placePiece(internalRepresentation[originalLine][originalColumn], new Move(tempLine, tempColumn));
				}
			}
		}

		/* Verificar a seguinte situacao (onde 0 sao as casas vazias,
		 * 1 e a casa dada pelos argumentos line e column, 2 e a casa
		 * com a qual faz "2 pontes" e 3 indica as casas vazias que
		 * estao entre elas):
		 *
		 * 02
		 * 33
		 * 10
		 */
		try {
			if (temporaryBoard.getBoard()[line-2][column+1] == player) {
				// Verificar se as casas entre a casa 1 e 2 estao vazias
				if (temporaryBoard.getBoard()[line-1][column] == Color.EMPTY
					&& temporaryBoard.getBoard()[line-1][column+1] == Color.EMPTY) {
					numberOfTwoBridges++;
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {}

		/* Verificar a seguinte situacao (onde 0 sao as casas vazias,
		 * 1 e a casa dada pelos argumentos line e column, 2 e a casa
		 * com a qual faz "2 pontes" e 3 indica as casas vazias que
		 * estao entre elas):
		 *
		 * 032
		 * 130
		 */
		try {
			if (temporaryBoard.getBoard()[line-1][column+2] == player) {
				// Verificar se as casas entre a casa 1 e 2 estao vazias
				if (temporaryBoard.getBoard()[line][column+1] == Color.EMPTY
					&& temporaryBoard.getBoard()[line-1][column+1] == Color.EMPTY) {
					numberOfTwoBridges++;
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {}

		/* Verificar a seguinte situacao (onde 0 sao as casas vazias,
		 * 1 e a casa dada pelos argumentos line e column, 2 e a casa
		 * com a qual faz "2 pontes" e 3 indica as casas vazias que
		 * estao entre elas):
		 *
		 * 23
		 * 31
		 */
		try {
			if (temporaryBoard.getBoard()[line-1][column-1] == player) {
				// Verificar se as casas entre a casa 1 e 2 estao vazias
				if (temporaryBoard.getBoard()[line][column-1] == Color.EMPTY
					&& temporaryBoard.getBoard()[line-1][column] == Color.EMPTY) {
					numberOfTwoBridges++;
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {}

		/* Verificar a seguinte situacao (onde 0 sao as casas vazias,
		 * 1 e a casa dada pelos argumentos line e column, 2 e a casa
		 * com a qual faz "2 pontes" e 3 indica as casas vazias que
		 * estao entre elas):
		 *
		 * 031
		 * 230
		 */
		try {
			if (temporaryBoard.getBoard()[line+1][column-2] == player) {
				// Verificar se as casas entre a casa 1 e 2 estao vazias
				if (temporaryBoard.getBoard()[line][column-1] == Color.EMPTY
					&& temporaryBoard.getBoard()[line+1][column-1] == Color.EMPTY) {
					numberOfTwoBridges++;
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {}

		/* Verificar a seguinte situacao (onde 0 sao as casas vazias,
		 * 1 e a casa dada pelos argumentos line e column, 2 e a casa
		 * com a qual faz "2 pontes" e 3 indica as casas vazias que
		 * estao entre elas):
		 *
		 * 01
		 * 33
		 * 20
		 */
		try {
			if (temporaryBoard.getBoard()[line+2][column-1] == player) {
				// Verificar se as casas entre a casa 1 e 2 estao vazias
				if (temporaryBoard.getBoard()[line+1][column] == Color.EMPTY
					&& temporaryBoard.getBoard()[line+1][column-1] == Color.EMPTY) {
					numberOfTwoBridges++;
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {}

		/* Verificar a seguinte situacao (onde 0 sao as casas vazias,
		 * 1 e a casa dada pelos argumentos line e column, 2 e a casa
		 * com a qual faz "2 pontes" e 3 indica as casas vazias que
		 * estao entre elas):
		 *
		 * 13
		 * 32
		 */
		try {
			if (temporaryBoard.getBoard()[line+1][column+1] == player) {
				// Verificar se as casas entre a casa 1 e 2 estao vazias
				if (temporaryBoard.getBoard()[line][column+1] == Color.EMPTY
					&& temporaryBoard.getBoard()[line+1][column] == Color.EMPTY) {
					numberOfTwoBridges++;
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {}

		return numberOfTwoBridges;
	}

	// private static int distanceBetweenBoardPlaces(Board board, int originLine, int originColumn, int destinyLine, int destinyColumn, int player, List<int[]> passedPositions) {
	// 	if (originLine == destinyLine && originColumn == destinyColumn)
	// 		return 0;
		
	// 	int distance = Integer.MAX_VALUE;

	// 	int opponent = Hex.otherPlayer(player);

	// 	for (int[] avaiablePosition : board.adjacentPositions(originLine, originColumn)) {
	// 		if 
	// 	if (board.getBoard()[originLine][originColumn+1] == opponent)
	// 		distance = Math.min(distance, distanceBetweenBoardPlaces(board, originLine, originColumn+1, destinyLine, destinyColumn, player));
	// 	if (board.getBoard()[originLine][originColumn-1] == opponent)
	// 		distance = Math.min(distance, distanceBetweenBoardPlaces(board, originLine, originColumn-1, destinyLine, destinyColumn, player));
	// 	if (board.getBoard()[originLine+1][originColumn] == opponent)
	// 		distance = Math.min(distance, distanceBetweenBoardPlaces(board, originLine+1, originColumn, destinyLine, destinyColumn, player));
	// 	if (board.getBoard()[originLine-1][originColumn+1] == opponent)
	// 		distance = Math.min(distance, distanceBetweenBoardPlaces(board, originLine-1, originColumn, destinyLine, destinyColumn, player));
	// 	if (board.getBoard()[originLine-1][originColumn+1] == opponent)
	// 		distance = Math.min(distance, distanceBetweenBoardPlaces(board, originLine-1, originColumn+1, destinyLine, destinyColumn, player));
	// 	if (board.getBoard()[originLine+1][originColumn+1] == opponent)
	// 		distance = Math.min(distance, distanceBetweenBoardPlaces(board, originLine, originColumn, destinyLine, destinyColumn, player));

	// 	// Caminho sem saida
	// 	if (distance == Integer.MAX_VALUE)
	// 		return -1;

	// 	return distance;
	// }

	/** Devolve o nome da IA.
	 *
	 * E usado nas interfaces para poder mostrar ao utilizador qual a
	 * IA que esta a seleccionar
	 * @returns O nome da IA
	 */
	public String getName() { return "Minimax"; }
}

